package sort;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

public class GuiBingSort3 {
    int [] temp;
    public  void guibingSort(int []  nums){
        if (nums.length==0){
            return;
        }
        temp=new int[nums.length];
        int lo=0;
        int hi=nums.length-1;
        sort(nums,lo,hi,temp);

    }

    public  void sort(int[] nums,int lo,int hi,int [] temp){
       if (lo>=hi){
           return;
       }
        int mid=(lo+hi)/2;
        sort(nums,lo,mid,temp);
        sort(nums,mid+1,hi,temp);
        merge(nums,lo,mid,hi,temp);
    }


    public  void  merge (int[] nums,int lo,int mid,int hi,int [] temp){
        int i=0;
        int j=lo;
        int k=mid+1;
        while (j<mid+1&&k<=hi){
            if (nums[j]<nums[k]){
                temp[i++]=nums[j++];
            }
            //todo:自己写这里少一个ｅｌｓｅ　　逻辑是十分严谨的

            else{
                temp[i++]=nums[k++];
            }
        }
//        todo:不能用if　　需要用while 这样才能循环起来
//        if (j<mid+1){
//            temp[i++]=nums[j++];
//        }
//        if (k<=hi){
//            temp[i++]=nums[k++];
//        }
        while (j<mid+1){
            temp[i++]=nums[j++];
        }
        while (k<=hi){
            temp[i++]=nums[k++];
        }
//        todo:　　temp数组已经是排完顺序的数组　但是要保证在原始数组上　所以需要对原始数组ａｒｒ进行修改


        for(int t=0;t<i;t++){
            nums[lo+t] = temp[t];
        }
    }


    public static void main(String[] args) {
        GuiBingSort3 guiBingSort3 = new GuiBingSort3();
        int[] nums=new int[] {5, 8, 2, 4, 1,7};
        guiBingSort3.guibingSort(nums);
        for (int a: nums
             ) {
            System.out.println(a);

        }
    }




}
